﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;

namespace Mindless
{
    /// <summary>
    /// A discontiguous "array" that can contain more than 2GB worth of items.
    /// </summary>
    class BigArray<T> : IList<T>
    {
        /// <summary>
        /// The contiguous chunks of items making up the array.
        /// </summary>
        protected T[/*iChunk*/][/*iT*/] chunks;

        /// <summary>
        /// .NET says we can't allocate more than 2GB at a time. We make sure to stay well under that.
        /// </summary>
        const int MAX_ALLOCATION_BYTES = (1 << 30);

        /// <summary>
        /// The size in bytes of the items stored in this type of array.
        /// </summary>
        static protected int ITEM_SIZE_BYTES = Marshal.SizeOf(default(T));

        /// <summary>
        /// Max number of items in a chunk.
        /// </summary>
        static protected int CHUNK_SIZE = MAX_ALLOCATION_BYTES / ITEM_SIZE_BYTES;

        /// <summary>
        /// Constructs an array that can contain the given number of items. Unlike a true array, the
        /// amount of memory required may exceed 2GB.
        /// </summary>
        public BigArray(int size)
        {
                // how many full-size chunks are needed
            int nFullChunks = size / CHUNK_SIZE;

                // might also need a partial-size chunk
            int nChunks = (size % CHUNK_SIZE == 0) ? nFullChunks : nFullChunks + 1;

                // allocate the memory...
            this.chunks = new T[nChunks][];

                // ... full-size chunks
            for (int iChunk = 0; iChunk < nFullChunks; ++iChunk)
                this.chunks[iChunk] = new T[CHUNK_SIZE];

                // ... partial-size chunk
            for (int iChunk = nFullChunks; iChunk < nChunks; ++iChunk)
                this.chunks[iChunk] = new T[size % CHUNK_SIZE];
        }

        #region Array-like Members

        /// <summary>
        /// Number of items in the receiver.
        /// </summary>
        public int Length
        {
            get { return this.Count; }
        }

        /// <summary>
        /// Initializes each item in the receiver via default(T).
        /// </summary>
        public void Initialize()
        {
            foreach (T[] chunk in this.chunks)
                chunk.Initialize();
        }

        /// <summary>
        /// Copies the given number of items from receiver to the given list, starting at the given index.
        /// </summary>
        public void CopyTo(IList<T> ts, int nItems, int tsIndex)
        {
            int count = 0;
            foreach (T[] chunk in this.chunks)
            {
                foreach (T t in chunk)
                {
                    if (count >= nItems)
                        return;
                    ts[tsIndex + count++] = t;
                }
            }
        }

        public void Sort(int iLeft, int iRight, Comparison<T> comparison)
        {
            Algorithm.Sort(this, iLeft, iRight, comparison);
        }

        #endregion

        #region IList<T> Members

        /// <summary>
        /// Answers the index of the given item in the receiver, or -1 if it is not present.
        /// </summary>
        public int IndexOf(T item)
        {
            int iGlobal = -1;
            for (int iChunk = 0; iChunk < this.chunks.Length; ++iChunk)
            {
                T[] chunk = this.chunks[iChunk];
                int iLocal = ((IList<T>) chunk).IndexOf(item);
                if (iLocal != -1)
                {
                    iGlobal = (iChunk * CHUNK_SIZE) + iLocal;
                    break;
                }
            }

            return iGlobal;
        }

        /// <summary>
        /// Can't insert into an array.
        /// </summary>
        public void Insert(int index, T item)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Can't remove from an array.
        /// </summary>
        public void RemoveAt(int index)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Accesses the item with the given index.
        /// </summary>
        public T this[int index]
        {
            get { return this.chunks[index / CHUNK_SIZE][index % CHUNK_SIZE]; }
            set { this.chunks[index / CHUNK_SIZE][index % CHUNK_SIZE] = value; }
        }

        #endregion

        #region ICollection<T> Members

        /// <summary>
        /// Can't add to an array.
        /// </summary>
        public void Add(T item)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Can't remove from an array.
        /// </summary>
        public void Clear()
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Indicates whether the receiver contains the given item.
        /// </summary>
        public bool Contains(T item)
        {
            return this.IndexOf(item) != -1;
        }

        /// <summary>
        /// Answers the number of items in the receiver.
        /// </summary>
        public int Count
        {
            get { return ((this.chunks.Length - 1) * CHUNK_SIZE) + this.chunks[this.chunks.Length-1].Length; }
        }

        /// <summary>
        /// Copies the receiver into the given array starting at the given index.
        /// </summary>
        public void CopyTo(T[] array, int arrayIndex)
        {
            this.CopyTo((IList<T>) array, this.Count, arrayIndex);
        }

        /// <summary>
        /// Indicates whether the receiver is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Can't remove from an array.
        /// </summary>
        public bool Remove(T item)
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable<T> Members

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            foreach (T[] chunk in this.chunks)
            {
                for (int iLocal = 0; iLocal < chunk.Length; ++iLocal)
                    yield return chunk[iLocal];
            }
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion
    }
}
